//
// Created by wangwanlong on 2024/7/11.
//

#ifndef MCGPP_SP_SET_H
#define MCGPP_SP_SET_H
#include <limits>
#include <string.h>
#include <memory>
#include "typedef.h"
namespace mcgpp{
  namespace sp {
    template<typename ValueType = int32_t>
    class SparseSet {
    public:
      explicit SparseSet(const ValueType k) :
              _size(0), _capacity(k),
              _sparse(new ValueType[2 * k]),
              _dense(nullptr) {
        _dense = _sparse + k;
        for (int i = 0; i < 2 * k; ++i)
          _sparse[i] = std::numeric_limits<ValueType>::max();

      }

      ~SparseSet() {
        delete[]_sparse;
        _sparse = nullptr;
        _dense = nullptr;

      }

      //容量必须是一致的
      SparseSet &operator=(SparseSet &other) {
        memcpy(_sparse, other._sparse, sizeof(ValueType) * _capacity);
        memcpy(_dense, other._dense, sizeof(ValueType) * other._size);
        _size = other._size;
        return *this;
      }

      ValueType &operator[](const ValueType &index) {
        return _dense[index];
      }


      ValueType size() const {
        return _size;
      }

      ValueType getValue(const ValueType index) {
        return _dense[index];
      }

      bool contains(const ValueType value) const {
        const ValueType index = _sparse[value];
        return index < _size && _dense[index] == value;
      }

      void add(const ValueType value) {
        const ValueType index = _sparse[value];
        if (index >= _size || _dense[index] != value) {
          _sparse[value] = _size;
          _dense[_size++] = value;
        }
      }

      //改变元素的表示
      void change(const ValueType old_val, const ValueType new_val) {
        const ValueType index = _sparse[old_val];
        _sparse[new_val] = index;
        _dense[index] = new_val;

      }

      //交换两个元素
      void swap(const ValueType u, const ValueType v) {
        std::swap(_dense[_sparse[u]], _dense[_sparse[v]]);
        std::swap(_sparse[u], _sparse[v]);

      }

      void remove(const ValueType value) {
        const ValueType index = _sparse[value];
        if (index < _size && _dense[index] == value) {
          const ValueType e = _dense[--_size];
          _dense[index] = e;
          _sparse[e] = index;
        }
      }

      const ValueType *begin() const {
        return _dense;
      }

      const ValueType *end() const {
        return _dense + _size;
      }

      void clear() {
        _size = 0;
      }

    public:

      ValueType _capacity;
      ValueType _size;
      ValueType *_sparse;//pos
      ValueType *_dense;//array
    };
  }
}
#endif //MCGPP_SP_SET_H
